ABSTRACT
The incredible rising of online networks show that these networks are complex and involving massive data.Giving
a very strong interest to set of techniques developed for mining these networks. The clique problem is a wellknown NP-Hard problem in graph mining. One of the fundamental applications for it is the community detection.
It helps to understand and model the network structure which has been a fundamental problem in several fields.
In literature, the exponentially increasing computation time of this problem make the quality of these solutions is
limited and infeasible for massive graphs. Furthermore, most of the proposed approaches are able to detect only
disjoint communities. In this paper, we present a new clique based approach for fast and efficient overlapping
community detection. The work overcomes the short falls of clique percolation method (CPM), one of most
popular and commonly used methods in this area. The shortfalls occur due to brute force algorithm for
enumerating maximal cliques and also the missing out many vertices thatleads to poor node coverage. The
proposed work overcome these shortfalls producing NMC method for enumerating maximal cliques then detects
overlapping communities using three different community scales based on three different depth levels to assure
high nodes coverage and detects the largest communities. The clustering coefficient and cluster density are used to
measure the quality. The work also provide experimental results on benchmark real world network to
demonstrate the efficiency and compare the new proposed algorithm with CPM method, The proposed algorithm
is able to quickly discover the maximal cliques and detects overlapping community with interesting remarks and
findings.
Keywords: - Graph Mining, Maximal clique problem, Overlapping community detection, Social network analysis